package demo;

public class Solution {
    //判断一个结点是否包含在一个子树中
    public boolean containNode(TreeNode root,TreeNode target){
        if(root==null){
            return false;
        }
        if(root==target){
            return true;
        }
        boolean leftResult=containNode(root.left,target);
        boolean rightResult=containNode(root.right,target);
        if(leftResult){
            return true;
        }
        return rightResult;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(p==root||q==root){
            return root;
        }
        boolean leftRes1=containNode(root.left,p);
        boolean leftRes2=containNode(root.left,q);

        if(leftRes1&&leftRes2){
            return lowestCommonAncestor(root.left,p,q);
        }
        if(!leftRes1&&!leftRes2){
            return lowestCommonAncestor(root.right,p,q);
        }
        return root;

    }
}
